package nowcoder.offer;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 数据流中的中位数
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-30 14:17
 */
public class GetMedian {

    LinkedList<Integer> list = new LinkedList<>();
    int len = 0;
    public void insert(Integer num){
        len++;
        //插入排序
        int index = 0;
        for (Integer i : list) {
            if (i > num) break;
            index++;
        }
        list.add(index,num);

    }


    public Double getMedian(){
        double res;
        if (len % 2 == 0)
            res = (list.get(len/2-1) + list.get(len/2)) / 2.0;
        else
            res = list.get(len/2) * 1.0;

        return res;
    }

    public static void main(String[] args) {
        GetMedian g = new GetMedian();
        g.insert(5);
        System.out.println(g.getMedian());
        g.insert(2);
        System.out.println(g.getMedian());
        g.insert(3);
        System.out.println(g.getMedian());
        g.insert(4);
        System.out.println(g.getMedian());
        g.insert(1);
        System.out.println(g.getMedian());
        g.insert(6);
        System.out.println(g.getMedian());
    }
}
